In mathematical optimization, the perturbation function is any function which relates to primal and dual problems. The name comes from the fact that any such function defines a perturbation of the initial problem. In many cases this takes the form of shifting the constraints.[1]
In some texts the value function is called the perturbation function, and the perturbation function is called the bifunction.[2]
Contents |
Given two dual pairs separated locally convex spaces and . Then given the function , we can define the primal problem by
If there are constraint conditions, these can be built in to the function by letting where is the indicator function. Then is a perturbation function if and only if .[1][3]
The duality gap is the difference of the right and left hand side of the inequality
where is the convex conjugate in both variables.[3][4]
For any choice of perturbation function F weak duality holds. There are a number of conditions which if satisfied imply strong duality.[3] For instance, if F is proper, jointly convex, lower semi-continuous with (where is the algebraic interior and is the projection onto Y defined by ) and X, Y are Fréchet spaces then strong duality holds.[1]
Let and be dual pairs. Given a primal problem (minimize f(x)) and a related perturbation function (F(x,y)) then the Lagrangian is the negative conjugate of F with respect to y (i.e. the concave conjugate). That is the Lagrangian is defined by
In particular the weak duality minmax equation can be shown to be
If the primal problem is given by
where . Then if the perturbation is given by
then the perturbation function is
Thus the connection to Lagrangian duality can be seen, as L can be trivially seen to be
Let and be dual pairs. Assume there exists a linear map with adjoint operator , and assume the primal objective function (including the constraints by way of the indicator function) can be written as such that . Then the perturbation function is given by
In particular if the primal objective is then the perturbation function is given by , which is the traditional definition of Fenchel duality.[5]